# Author    :Dun_Hz
# Time      :2024/3/15 15:45
# 基于快速排序的分治方法求列表第k大元素
def selectTopK(a,low,high,k):
    if low==high and k==0:
        return a[0]
    pivotkey = a[high]
    i,j=low,high
    while i<j:
        while i<j and a[i]<=pivotkey:
            i+=1
        a[i],a[j] = a[j],a[i]
        while i<j and a[j]>=pivotkey:
            j -=1
        a[i], a[j] = a[j], a[i]
    print(a)
    if k<i:
        return selectTopK(a,low,i-1,k)
    elif k >i:
        return selectTopK(a,i+1,high,k)
    else:
        return a[i]

a=[1,5,4,3,2]
print(selectTopK(a,0,len(a)-1,2))
